The invention pertains to computer network protocols and computer programs that implement such protocols.
There are many instances in which it would be advantageous to be able to advance and retard data transfer rates during network data transmissions to make full use of the available bandwidth based on the current network traffic. One such instance occurs when multi-player games are played over a network, such as the Internet. The executable code for these games are often located on network servers that are accessible through various networks, such as the Internet. Alternately, some or all of the executable code for the games may be located on each of computers the players are using. One or more players can log on to the game and play against the game itself (a computer) or each other. These games typically comprise an ever-changing graphical environment that is primarily controlled by the control inputs of the various game players. For example, a game may involve several warriors facing off against one another, with one or more of the warriors being controlled by each player (or a computer). In such a game, the movements of each warrior relative to the graphical environment and the other warriors will depend on the control inputs of the players (or automated movements by the computer). For this reason, it is highly desired to transfer the user-input information to the game as rapidly as possible so that the inputs for the various players can be immediately reflected by updating the graphics displayed on each player""s screen.
To understand why rapid data transfer is so desirable, consider a situation in which the data transfer carries a substantial delay. Player A activates her controls to cause one of her warriors to throw a spear at an enemy warrior. Player A aims the spear based on her perception of the current state of the game, i.e., what she sees on her screen. If the data transfer rate is rapid, the display each player sees accurately reflects (is synchronous with) the current state of the game. Conversely, if the data transfer carries a delay, the display each player sees does not accurately reflect the present game statexe2x80x94that is, the displays observed by the various players will not be synchronized. Under such circumstances, the players may miss their targets due to the program""s inaccurate display of the positions of the other participants. This delay may also cause players to be unaware of an attack in progress from another player. Transfer delays of this type are frequently encountered when networked games are played, creating unsatisfactory game performance. A principle reason for this is conventional program development tools do not provide a built-in interface that allows the data transfer rate to be adjusted to optimize bandwidth use under varying link conditions.
Developers of multi-player networked game applications typically design games to support presumed worst-case bandwidth situations. As a result, the bandwidth usage between machines is limited to a fraction of the bandwidth available over the network link, which results in non-optimal game performance. Under such worst-case-scenario design practices, the game developer assumes a minimum available link bandwidth, such as 14.4 or 28.8 kilobaud (kilobits per second), and a maximum number of players the game will support or likely encounter. The developer may also determine the average (or maximum) size of each message that the game will transfer over the network (which she typically will seek to minimize). The developer will then calculate a maximum message sending rate based on this predetermined criteria, and the game application will send messages at this calculated transfer rate. For example, in a peer-to-peer game, where messages are distributed to all players from each machine, the following equation can be used to determine the maximum sending rate:                     R        =                  bw                      cb            *                          (                              n                -                1                            )                                                          (        1        )            
wherein R is the maximum message sending rate in messages per second, n is the number of players in the game, cb is the number of bytes in a message, and bw is the assumed bandwidth.
Unfortunately, the use of static calculations of this sort leads to a number of problems, including: (1) the application can""t compensate for variation in headers due to the underlying transport; (2) the application will under-utilize the link in situations where more bandwidth is available than originally presumed; and (3) the application will not be able to adjust the message sending rate to compensate for other traffic on the link. In addition, when the conditions on the link are actually worse than the initial assumptions,sending messages at the statically-deterrnined rate will lead to the link being backlogged. That is, the rate at which the application sends messages may exceed the link""s capabilities, causing messages to build up in the sending computer or on a router in the network, resulting in: increased apparent latency that can grow without bound, eventually making the game unplayable and ultimately causing the link to timeout.
A solution to all of the above problems is for the application to be able to make on-the-fly changes to the message send rate based on continuous measurements of the varying link conditions. In order to provide a platform (i.e. programming interface) for this solution, the platform must be able to determine the actual available bandwidth between two computers on a continuous basis. It is also preferable that the platform be able to detect link saturation and clear out backlogged messages. The platform must then be able to inform the application of the available bandwidth and link conditions so that the transmission code in the application can adapt to the prevailing network conditions.
The invention addresses the foregoing problems by providing a network communication protocol and associated methods for implementing the protocol that enable application programs to tune message send rates to optimize use of the available network bandwidth under varying network conditions. The network protocol is preferably implemented in an application program interface (API) that allows programmers to use features of the invention through a set of API calls. The network protocol resides at the application layer, providing a tool for application programs to use a variety of network protocol suites, including TCP/IP and IPX/SPX.
According to a first aspect of the invention, the network protocol allows application programs to determine the available bandwidth between two computers that are linked in communication across a network. Outbound messages are sent from a first local computer to a second remote computer, with the remote computer returning an acknowledge message for each outbound message. The local computer records the send time for each outbound message and includes a message identifier in the message. Each acknowledge message is timestamped with the time it is sent from the remote computer, and includes a count of the bytes received from the local computer and an identifier that matches the message identifier of the corresponding outbound message. The message identifier is used to ensure that the acknowledgement messages are correctly matched with outbound messages. A clock bias between the computers is calculated based on the local time the outbound messages are sent and the remote time they are received by comparing the send times with the acknowledge message timestamps. The rate the outbound messages are sent is increased until the link becomes saturated, which is detected by observing an increase in outbound latency based on changes in clock bias and roundtrip latency. The outbound bandwidth is calculated by calculating a difference in bytes received based on the byte counts in acknowledgement messages, and dividing the result by a difference in the time stamps of the acknowledgement messages.
According to another aspect of the invention, the network protocol facilitates a method for maintaining a clock offset between two computers linked in communication across a network. The method comprises sending messages between a first local computer and a second remote computer across the network, whereby receipt of the local computer""s messages are acknowledged by the remote computer. Local send times in local clock time and timestamps based on remote clock times are tracked to calculate a clock offset between the two computers. The clock offset preferably is continually tracked and updated during transmission of multiple messages.
The network protocol and associated methods allows application programs to maximize the use of available network bandwidth, thereby improving the performance of the program. A plurality of messages is sent from a first computer linked in communication to a second computer across a network while increasing the rate the messages are sent according to a predetermined scheme until link saturation (and detection thereof) occurs, creating a backlog of messages. The predetermined scheme also continuously pushes up the send rate until message dropouts are detected, at which point it makes a step reduction of the send rate, and starts pushing up the send rate again. The link saturation and detection may also result from increased link usage by other users on the network. The present bandwidth of the link is then calculated, along with a wait time for stalling issuance of any new messages until the backlogged messages are cleared. Issuance of messages are then stalled for the wait time, and the message send rate is throttled back to the calculated bandwidth, and then the rate at which messages are sent is ramped up again. The process preferably is repeated on a continual basis so as to adjust the message send rate to take advantage of the latest bandwidth and backlog measurements.
The foregoing methods can also be implemented in application programs that enable more than two computers to be linked in communication across a network, such as the case that exists when multiple players in a peer-to-peer relationship to one another are playing a game over a network. The message send rate can be tuned for each peer-to-peer relationship, maximizing the use of available bandwidth across the peer-to-peer link.
Further advantages and features of the invention will become apparent with reference to the following detailed description and accompanying drawings.